\input{euler.tex}

\begin{document}

\problem[336]{Maximix Arrangements}

A train is used to transport four carriages in the order: $ABCD$. However, sometimes when the train arrives to collect the carriages, they are not in the correct order.

To rearrange the carriages, they are all shunted on to a large rotating turntable. After the carriages are uncoupled at a specific point, the train moves off the turntable pulling the carriages still attached with it. The remaining carriages are rotated 180 degrees. All of the carriages are then rejoined and this process is repeated as often as necessary in order to obtain the least number of uses of the turntable.

Some arrangements, such as $ADCB$, can be solved easily: the carriages are separated between $A$ and $D$, and after $DCB$ are rotated the correct order has been achieved.

However, Simple Simon, the train driver, is not known for his efficiency, so he always solves the problem by initially getting carriage $A$ in the correct place, then carriage $B$, and so on.

Using four carriages, the worst possible arrangements for Simon, which we shall call \emph{maximix} arrangements, are $DACB$ and $DBAC$; each requiring him five rotations (although, using the most efficient approach, they could be solved using just three rotations). The process he uses for $DACB$ is shown below.
\[
D|ACB \rightarrow |DBCA \rightarrow AC|BD \rightarrow A|CDB \rightarrow AB|DC \rightarrow ABCD
\]

It can be verified that there are 24 maximix arrangements for six carriages, of which the tenth lexicographic maximix arrangement is $DFAECB$.

Find the $2011^{\text{th}}$ lexicographic maximix arrangement for eleven carriages.

\solution

It is easy to see that in a maximix arrangement, it takes two rotations to arrange each of $A, B, C, \ldots$ in order, until there are two carriages left, where it takes one more rotation to swap them in order. So the total number of rotations required to reorder a maximix arrangement is $2 \times (n-2)+1$.

Consider the two rotations required to get $A$ in place within a sequence of length $(n+1)$. Obviously $A$ must be somewhere in the middle of the sequence, so the sequence looks like the following:
\begin{equation}
x_1, \ldots, x_m, A, x_{m+1}, \ldots, x_n . \label{eq:336.1}
\end{equation}
Cutting off before $A$ and rotating everything that follows $A$ (including $A$) leads to
\begin{equation}
x_1, \ldots, x_m, x_n, \ldots, x_{m+1}, A . \label{eq:336.2}
\end{equation}
Then rotating the entire sequence leads to 
\begin{equation}
A, x_{m+1}, \ldots, x_n, x_m, \ldots, x_1 . \label{eq:336.3}
\end{equation}

In order for sequence \eqref{eq:336.1} to be a maximix arrangement of length $(n + 1)$, the sub-sequence in \eqref{eq:336.3} after $A$ must be a maximix sequence of length $n$, and \eqref{eq:336.3} can be written as
\begin{equation}
A, y_1, \ldots, y_k, y_{k+1}, \ldots, y_n . \label{eq:336.4}
\end{equation}
Comparing \eqref{eq:336.4} with \eqref{eq:336.3}, we find that a maximix sequence of length $(n+1)$ can be generated from a maximix sequence of length $n$ by the following:
\begin{equation}
y_n, \ldots, y_{k+1}, A, y_1, \ldots, y_k , \label{eq:336.5}
\end{equation}
where $1 \le k \le n-1$ is an arbitrary position to cut and rearrange the $n$-length sequence. This formula allows us to generate all maximix sequences of length $n+1$ from maximix sequences of length $n$.

Finally, to have an idea about the scale of the problem, let $p(n)$ be the number of maximix sequences of length $n$. It is easy to find that
\[
p(n+1) = p(n) \times (n-1) , 
\]
with $p(2) = 1$. Therefore, 
\[
p(n) = (n-2)! 
\]
for $n \ge 2$. For this problem, $N = 11$ and $p(N) = 362880$. This scale is not large. Therefore, we are comfortable to generate all maximix arrangements of eleven carriages and then find the $2011^{\text{th}}$ arrangement.

\complexity

For each $(n-1)$-length sequence, $(n-2)$ number of $n$-length sequences can be generated using \eqref{eq:336.5}, where generating each takes $\BigO(n-1)$ assignments. So it takes $\BigO((n-1)!)$ time to generate all sequences of length $n$ from sequences of length $(n-1)$. There are $N$ such sequences, so the total time is $\BigO(N!)$.

Finding the $2011^{\text{th}}$ element takes linear time on average.

Time complexity: $\BigO(N!)$.

Space complexity: $\BigO((N-2)!)$.

\answer

$CAGBIHEFJDK$

\end{document} 
